package A一周刷爆LeetCode.A基础班.H前缀树和贪心算法;

import java.util.PriorityQueue;

/**
 * @author wei.zhao
 * @description: 切割金条
 * @date 2022年03月25日 11:07
 */
public class Code04_LessMoneySplitGold {

    public static int lessMoney(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        int result = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i : arr) {
            queue.add(i);
        }
        while (queue.size() != 1) {
            Integer i1 = queue.poll();
            Integer i2 = queue.poll();
            result = result + i1 + i2;
            queue.add(i1 + i2);
        }
        return result;
    }

}
